/*
 * @lc app=leetcode.cn id=401 lang=cpp
 *
 * [401] 二进制手表
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<string> ans;
    string valid(int arr)
    {
        int low6 = arr & ((1 << 6) - 1);
        int high4 = arr >> 6;
        string res;
        if (low6 >= 0 && low6 <= 59 && high4 >= 0 && high4 <= 11)
        {
            res += to_string(high4);
            res += ":";
            if (low6 < 10)
                res += '0';
            res += to_string(low6);
        }
        return res;
    }
    void dfs(int arr, int pos, int num)
    {
        if (num == 0)
        {
            auto res = valid(arr);
            if (res.size())
                ans.push_back(res);
            return;
        }
        if (pos == 10)
            return;

        dfs(arr, pos + 1, num);
        arr |= 1 << pos;
        dfs(arr, pos + 1, num - 1);
    }
    vector<string> readBinaryWatch(int turnedOn)
    {
        int ons = 0;
        dfs(ons, 0, turnedOn);
        return ans;
    }
};
// @lc code=end
